/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/hash-function
   @Language: C++
   @Datetime: 16-02-09 04:49
   */

class Solution {
public:
	/**
	 * @param key: A String you should hash
	 * @param HASH_SIZE: An integer
	 * @return an integer
	 */
	int hashCode(string key,int HASH_SIZE) {
		// write your code here
		long h,r,i;
		for(h=0,r=1,i=key.length(); i--;){
			h += key[i]*r;
			h = (h>INT_MAX ? h%HASH_SIZE : h);
			r *= 33;
			r = (r>INT_MAX ? r%HASH_SIZE : r);
		}
		return h%HASH_SIZE;
	}
};
